package com.kevin.Code.Array;

/**
 * @author Vinlee Xiao
 * @Classname DiagonalTraverse
 * @Description Leetcode 498. 对角线遍历 中等难度 代码写的不好
 * @Date 2021/12/11 11:35
 * @Version 1.0
 */
public class DiagonalTraverse {

    /**
     * 对角线遍历
     *
     * @param mat
     * @return
     */
    public int[] findDiagonalOrder(int[][] mat) {
        int row = mat.length;
        int col = mat[0].length;
        //最终返回的结果数组
        int[] result = new int[row * col];
        //两个特殊情况特殊处理
        if (row == 1) {
            for (int i = 0; i < col; i++) {
                result[i] = mat[0][i];
            }
            return result;
        }
        if (col == 1) {

            for (int i = 0; i < row; i++) {
                result[i] = mat[i][0];
            }
            return result;
        }
        //行列数之和为0-(M+N-2)
        int digonalSum = row + col - 2;
        int startX = 0;
        int startY = 0;
        int cnt = 0;
        for (int i = 0; i <= digonalSum; i++) {
            //当为偶数时向上遍历
            //确定开始遍历的坐标
            if (i % 2 == 0) {
                if (i < row) {
                    startX = i;
                    startY = 0;
                } else if (i >= row) {
                    startX = row - 1;
                    startY = i - startX;
                }
                while (startX >= 0 && startY < col) {

                    result[cnt] = mat[startX][startY];
                    startX -= 1;
                    startY = i - startX;
                    cnt++;
                }
                //为奇数时向下遍历
            } else {

                if (i < col) {
                    startX = 0;
                    startY = i;
                } else if (i >= col) {
                    startY = col - 1;
                    startX = i - startY;
                }
                while (startX < row && startY >= 0) {
                    result[cnt] = mat[startX][startY];
                    startY -= 1;
                    startX = i - startY;
                    cnt++;
                }
            }
        }
        //停止遍历的坐标 (row-1)(col-1)
        return result;
    }

    public static void main(String[] args) {
        int[][] nums = new int[][]{{3}};
        DiagonalTraverse diagonalTraverse = new DiagonalTraverse();
        int[] order = diagonalTraverse.findDiagonalOrder(nums);
        for (int i : order) {
            System.out.print(i + " ");
        }
    }
}
